package leetCode;

public class Q746 {
    /**
     * 给你一个整数数组 cost ，
     * cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
     * 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * 请你计算并返回达到楼梯顶部的最低花费。
     */
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;

        //dp[i] 表示登到台阶i的最低花费,
        int[] dp = new int[len+1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i=2;i<=len;i++){
            /**
             * 从上一个台阶需要花费dp[i-1]+cost[i-1]
             * 从上上个台阶需要花费dp[i-2]+cost[i-2]
             */
            int expend1 = dp[i-1]+cost[i-1];
            int expend2 = dp[i-2]+cost[i-2];
            dp[i] = Math.min(expend1,expend2);
        }

        return dp[len];
    }
}
